package model.algorithms.embedding;

import java.util.ArrayList;
import java.util.List;

import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;
import ilog.cplex.IloCplex.UnknownObjectException;

import model.components.links.link.VirtualLink;
import model.components.links.link.PhysicalLink;
import model.components.networks.network.Network;
import model.components.networks.network.VirtualNetwork;
import model.components.networks.network.PhysicalNetwork;
import model.components.nodes.node.VirtualNode;
import model.components.nodes.node.PhysicalNode;
import model.components.nodes.node.Node;

public class EmbeddingAlgorithm
{	
	private String name;
	public String getName(){ return name; }
	public void setName( String name ){ this.name = name; }

	/** Amount of traffic for the virtual links routed over the physical links. */
	private double fValues[][][];
	public double[][][] getFValues(){ return fValues; }
	public void setFValues( double fValues[][][] ){ this.fValues = fValues; }
	
	/** Binary variables set to 1 if there is traffic flow of the virtual links via physical links. */
	private double xValues[][][];
	public double[][][] getXValues(){ return xValues; }
	public void setXValues( double xValues[][][] ){ this.xValues = xValues; }
	
	public EmbeddingAlgorithm( String name )
	{
		this.setName( name );
	}
	
	public boolean run( VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork )
	{
    	boolean isSolve = false;
		
		try
		{
			PhysicalNetwork augmentedPhysicalNetwork = this.augmentedPhysicalNetwork( virtualNetwork, physicalNetwork );
			
			IloNumVar f[][][] = new IloNumVar[ virtualNetwork.getVirtualLinks().size() ][ augmentedPhysicalNetwork.getNodes().size() ][ augmentedPhysicalNetwork.getNodes().size() ];
			IloNumVar x[][][] = new IloNumVar[ virtualNetwork.getVirtualLinks().size() ][ augmentedPhysicalNetwork.getNodes().size() ][ augmentedPhysicalNetwork.getNodes().size() ];
			
			IloCplex cplex = this.setCplex( new IloCplex() );
			cplex.setOut( null );
			this.setConstrains( cplex, f, x, virtualNetwork, physicalNetwork, augmentedPhysicalNetwork );
			this.minimize( cplex, f, x, virtualNetwork, physicalNetwork, augmentedPhysicalNetwork );
			
			isSolve = cplex.solve();
			
			if( isSolve )
			{
				this.setFValues( this.fValues( cplex, f, virtualNetwork, augmentedPhysicalNetwork ) );
				this.setXValues( this.xValues( cplex, x, virtualNetwork, augmentedPhysicalNetwork ) );
			}
				
			cplex.end();
		}
		catch( IloException e )
		{
			System.err.println( "Concert exception caught: " + e );
		}
		
		return isSolve;
	}
	
	private PhysicalNetwork augmentedPhysicalNetwork( VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork )
	{
    	PhysicalNetwork copyPhysicalNetwork = physicalNetwork.getCopy();
		
		for( PhysicalNode copyPhysicalNode: copyPhysicalNetwork.getPhysicalNodes() )
			copyPhysicalNode.setNumber( copyPhysicalNode.getNumber() + virtualNetwork.getNodes().size() );
		
		PhysicalNetwork augmentedPhysicalNetwork = new PhysicalNetwork( "augmentedPhysicalNetwork" );//, 0, null, 0, 0, 0, "", 0, 0, 0, 0, 0, 0, 0, 0 );
		//PhysicalNetwork augmentedPhysicalNetwork = new PhysicalNetwork( "augmentedPhysicalNetwork", 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, "", 0, 0, 0, 0, 0, 0, 0, 0 );
		
		for( PhysicalLink physicalLink: copyPhysicalNetwork.getPhysicalLinks() )
			augmentedPhysicalNetwork.addLinkAndNodes( physicalLink, physicalLink.getFirstNode(), physicalLink.getSecondNode() );
		
		int i = augmentedPhysicalNetwork.getPhysicalLinks().size() + 1;
		
		for( VirtualNode virtualNode: virtualNetwork.getVirtualNodes() )
			for( PhysicalNode copyPhysicalNode: copyPhysicalNetwork.getPhysicalNodes() )
				augmentedPhysicalNetwork.addLinkAndNodes( new PhysicalLink( physicalNetwork.getName(), i++, Integer.MAX_VALUE, 0 ), virtualNode, copyPhysicalNode );
		
    	return augmentedPhysicalNetwork;
	}
	
	private IloCplex setCplex( IloCplex cplex ) throws IloException
	{
		cplex.setParam( IloCplex.DoubleParam.TiLim, 600 );
		cplex.setParam( IloCplex.DoubleParam.ObjULim, Double.MAX_VALUE );
		cplex.setParam( IloCplex.DoubleParam.ObjLLim, -1 * Double.MAX_VALUE );
		
		return cplex;
	}
	
	private void setConstrains( IloCplex cplex, IloNumVar f[][][], IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{		
		this.setDomainConstrains( cplex, f, x, virtualNetwork, augmentedPhysicalNetwork );
		this.setNodeCapacitiesConstrains( cplex, f, virtualNetwork, physicalNetwork );
		this.setLinkCapacitiesConstrains( cplex, f, x, virtualNetwork, augmentedPhysicalNetwork );
		this.setFlowConstrains( cplex, f, virtualNetwork, augmentedPhysicalNetwork );
		this.setOneNodeConstrains( cplex, x, virtualNetwork, physicalNetwork );
		this.setSameTypeConstrains( cplex, x, virtualNetwork, physicalNetwork, augmentedPhysicalNetwork );
		this.setXConstrains( cplex, f, x, virtualNetwork, augmentedPhysicalNetwork );
		this.setGraphConnectedConstrains( cplex, x, virtualNetwork, augmentedPhysicalNetwork );
		this.setMatchingConstrains( cplex, x, virtualNetwork, physicalNetwork );
	}
	private void setDomainConstrains( IloCplex cplex, IloNumVar f[][][], IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				f[ i ][ u ] = cplex.numVarArray( augmentedPhysicalNetwork.getNodes().size(), 0, Double.MAX_VALUE );	// (1)
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				x[ i ][ u ] = cplex.numVarArray( augmentedPhysicalNetwork.getNodes().size(), 0, 1 );	// (2)
	}
	private void setNodeCapacitiesConstrains( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork ) throws IloException
	{
		double virtualNodesCapacities[][] = virtualNetwork.getNodesCapacities();
		double availablePhysicalNodesCapacities[][] = physicalNetwork.getPhysicalNodesAvailableCapacities();
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int a = 0; a < this.nodesNumberByType( physicalNetwork ).size(); a++ )
				for( int w: this.nodesNumberByType( physicalNetwork ).get( a ) )
					for( int m: this.nodesNumberByType( virtualNetwork ).get( a ) )
						for( int j = 0; j < 3; j++ )
							cplex.addLe( cplex.prod( virtualNodesCapacities[ j ][ m ], x[ i ][ m ][ w + virtualNetwork.getNodes().size() ] ), availablePhysicalNodesCapacities[ j ][ w ] );
	}
	private void setLinkCapacitiesConstrains( IloCplex cplex, IloNumVar f[][][], IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		// Summation of flows on both directions of the undirected link remains within its available bandwidth
		double availablePhysicalBandwidth[][] = augmentedPhysicalNetwork.getPhysicalLinksAvailableBandwidths();
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = virtualNetwork.getNodes().size(); u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				for( int v = virtualNetwork.getNodes().size(); v < augmentedPhysicalNetwork.getNodes().size(); v++ )
					cplex.addLe( cplex.sum( f[ i ][ u ][ v ], f[ i ][ v ][ u ] ), cplex.prod( availablePhysicalBandwidth[ u ][ v ], x[ i ][ u ][ v ] ) );	// (1)
		
		for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
			for( int v = 0; v < augmentedPhysicalNetwork.getNodes().size(); v++ )
			{
				IloNumExpr virtualBandwidth = cplex.prod( x[ 0 ][ 0 ][ 0 ], 0 );
				
				for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
					virtualBandwidth = cplex.sum( f[ i ][ u ][ v ], f[ i ][ v ][ u ] );
				
				cplex.addLe( virtualBandwidth, availablePhysicalBandwidth[ u ][ v ] );	// (2)
			}
	}
	private void setFlowConstrains( IloCplex cplex, IloNumVar f[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		// The net flow to a node is zero, except for the source node and the sink node
		
		int source[] = new int[ virtualNetwork.getVirtualLinks().size() ];
		int sink[]   = new int[ virtualNetwork.getVirtualLinks().size() ];

		for( VirtualLink virtualLink: virtualNetwork.getVirtualLinks() )
		{
			source[  virtualLink.getNumber() ] = virtualLink.getFirstNode().getNumber();
			sink[    virtualLink.getNumber() ] = virtualLink.getSecondNode().getNumber();
		}

		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				if( u != source[ i ] && u != sink[ i ] )
				{
					IloLinearNumExpr mappedVirtualBandwidth = cplex.linearNumExpr();
				
					for( int w = 0; w < augmentedPhysicalNetwork.getNodes().size(); w++ )
					{
						mappedVirtualBandwidth.addTerm(  1, f[ i ][ u ][ w ] );
						mappedVirtualBandwidth.addTerm( -1, f[ i ][ w ][ u ] );
					}
				
					cplex.addEq( mappedVirtualBandwidth, 0 );	// (1)
				}
		
		double virtualBandwidths[][] = virtualNetwork.getBandwidths();

		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
		{
			IloLinearNumExpr mappedVirtualBandwidth = cplex.linearNumExpr();
			
			for( int w = 0; w < augmentedPhysicalNetwork.getNodes().size(); w++ )
			{
				mappedVirtualBandwidth.addTerm(  1, f[ i ][ source[ i ] ][ w ] );
				mappedVirtualBandwidth.addTerm( -1, f[ i ][ w ][ source[ i ] ] );
			}
			
			cplex.addEq( mappedVirtualBandwidth, virtualBandwidths[ source[ i ] ][ sink[ i ] ] );	// (2)
		}
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
		{
			IloLinearNumExpr mappedVirtualBandwidth = cplex.linearNumExpr();

			for( int w = 0; w < augmentedPhysicalNetwork.getNodes().size(); w++ )
			{
				mappedVirtualBandwidth.addTerm(  1, f[ i ][ sink[ i ] ][ w ] );
				mappedVirtualBandwidth.addTerm( -1, f[ i ][ w ][ sink[ i ] ] );
			}
			
			cplex.addEq( mappedVirtualBandwidth, -virtualBandwidths[ source[ i ] ][ sink[ i ] ] );	// (3) 
		}
	}
	private void setOneNodeConstrains( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork ) throws IloException
	{
		// Only one substrate node is selected for each request node.
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int a = 0; a < this.nodesNumberByType( physicalNetwork ).size(); a++ )
				for( int m: this.nodesNumberByType( virtualNetwork ).get( a ) )
				{
					IloLinearNumExpr nodesNumber = cplex.linearNumExpr();
					
					for( int w: this.nodesNumberByType( physicalNetwork ).get( a ) )
						nodesNumber.addTerm( x[ i ][ m ][ w + virtualNetwork.getNodes().size() ], 1 );
					
					cplex.addEq( nodesNumber, 1 );
				}
	}
	private void setSameTypeConstrains( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		// At most one request node is linked to a substrate node of the same type.
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int a = 0; a < this.nodesNumberByType( physicalNetwork ).size(); a++ )
				for( int w: this.nodesNumberByType( physicalNetwork ).get( a ) )
				{
					IloLinearNumExpr sameType = cplex.linearNumExpr();
					
					for( int m: this.nodesNumberByType( virtualNetwork ).get( a ) )
						sameType.addTerm( x[ i ][ m ][ w + virtualNetwork.getNodes().size() ], 1 );
					
					cplex.addLe( sameType, 1 );	// (1)
				}
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int m = 0; m < virtualNetwork.getNodes().size(); m++ )
			{
				IloLinearNumExpr sameType = cplex.linearNumExpr();
				
				for( int w = virtualNetwork.getNodes().size(); w < augmentedPhysicalNetwork.getNodes().size(); w++ )
					sameType.addTerm( x[ i ][ m ][ w ], 1 );
				
				cplex.addLe( sameType, 1 );	// (2)
			}
	}
	private void setXConstrains( IloCplex cplex, IloNumVar f[][][], IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		// x is set whenever there is any flow in either direction of the substrate link.
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				for( int v = 0; v < augmentedPhysicalNetwork.getNodes().size(); v++ )
					cplex.addGe( cplex.sum( f[ i ][ u ][ v ], f[ i ][ v ][ u ] ), x[ i ][ u ][ v ] );	// (1)
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int u = 0; u < augmentedPhysicalNetwork.getNodes().size(); u++ )
				for( int v = 0; v < augmentedPhysicalNetwork.getNodes().size(); v++ )
					cplex.addEq( x[ i ][ u ][ v ], x[ i ][ v ][ u ] );	// (2)
	}
	private void setGraphConnectedConstrains( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException
	{
		// Resource mapping solution is a connected graph.
		
		for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
			for( int j = 0; j < virtualNetwork.getVirtualLinks().size(); j++ )
				for( int u = 0; u < virtualNetwork.getNodes().size(); u++ )
					for( int v = virtualNetwork.getNodes().size(); v < augmentedPhysicalNetwork.getNodes().size(); v++ )
						cplex.addEq( x[ i ][ u ][ v ], x[ j ][ u ][ v ] );	// (1)
	}
	private void setMatchingConstrains( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork ) throws IloException
	{
		// Matching constraint.
		
    	for( Node nodSub: physicalNetwork.getNodes() )
			for( Node nodReq: virtualNetwork.getNodes() )
				if( !nodSub.getType().equals( nodReq.getType() ) || !nodSub.getOperatingSystem().equals( nodReq.getOperatingSystem() ) || !nodSub.getVirtualEnvironment().equals( nodReq.getVirtualEnvironment() ) )
					for( int i = 0; i < virtualNetwork.getVirtualLinks().size(); i++ )
						cplex.addEq( x[ i ][ nodReq.getNumber() ][ nodSub.getNumber() + virtualNetwork.getNodes().size() ], 0 );
	}

	protected void minimize( IloCplex cplex, IloNumVar f[][][], IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork physicalNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws IloException{}
	
	private double[][][] fValues( IloCplex cplex, IloNumVar f[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws UnknownObjectException, IloException
	{
		double fValues[][][] = new double[ virtualNetwork.getVirtualLinks().size() ][ augmentedPhysicalNetwork.getNodes().size() ][ augmentedPhysicalNetwork.getNodes().size() ];
		
		for( int k = 0; k < virtualNetwork.getVirtualLinks().size(); k++ )
			for( int i = 0; i < augmentedPhysicalNetwork.getNodes().size(); i++ )
				fValues[ k ][ i ] = cplex.getValues( f[ k ][ i ] );
		
		return fValues;
	}
	private double[][][] xValues( IloCplex cplex, IloNumVar x[][][], VirtualNetwork virtualNetwork, PhysicalNetwork augmentedPhysicalNetwork ) throws UnknownObjectException, IloException
	{
		double xValues[][][] = new double[ virtualNetwork.getVirtualLinks().size() ][ augmentedPhysicalNetwork.getNodes().size() ][ augmentedPhysicalNetwork.getNodes().size() ];
		
		for( int k = 0; k < virtualNetwork.getVirtualLinks().size(); k++ )
			for( int i = 0; i < augmentedPhysicalNetwork.getNodes().size(); i++ )
				xValues[ k ][ i ] = cplex.getValues( x[ k ][ i ] );
		
		return xValues;
	}
	
	public List< List< Integer > > nodesNumberByType( Network network )
	{	
		List< List< Integer > > nodesNumberByType = new  ArrayList< List< Integer > >();
		
		for( int i = 0; i < 3; i++ )
			nodesNumberByType.add( new ArrayList< Integer >() );
		
		for( int i = 0; i < network.getNodes().size(); i++ )
		{
			String nodeType = network.getNodes().get( i ).getType();
			
			if( nodeType.equals( Node.ROUTER_TYPE ) )
				nodesNumberByType.get( 0 ).add( i );
			
			else if( nodeType.equals( Node.SWITCH_TYPE ) )
				nodesNumberByType.get( 1 ).add( i );
			
			else if( nodeType.equals( Node.SERVER_TYPE ) )
				nodesNumberByType.get( 2 ).add( i );
		}
		
		return nodesNumberByType;
	}
	
	
}
